package arithmetic.LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.jupiter.api.Test;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui
 * -chang-zi-chuan-by-leetc-2/
 *
 * @author jiangfeng on 2022/9/30
 */
public class MaxNoRepeat {

    @Test
    public void test() {
        System.out.println(lengthOfLongestSubstring2("acbceha"));
        System.out.println(lengthOfLongestSubstring2("acbtehy"));
    }

    public int lengthOfLongestSubstring(String s) {
        char[] arr = s.toCharArray();
        // 记录每个字符出现的最大位置
        Map<Character, Integer> map = new HashMap<>(arr.length);
        int maxLen = 0, start = 0;
        for (int i = 0; i < arr.length; i++) {
            Integer lastIndex = map.get(arr[i]);
            if (lastIndex != null) {
                start = Math.max(start, lastIndex);
            }
            maxLen = Math.max(maxLen, i - start + 1);
            map.put(arr[i], i);
        }

        return maxLen;

    }

    // 滑动窗口
    public int lengthOfLongestSubstring2(String s) {
        char[] arr = s.toCharArray();
        // 记录每个字符出现的最大位置
        Set<Character> set = new HashSet<>(arr.length);
        int left = 0, right = 0, result = 0;
        while (right < arr.length) {
            if (!set.contains(arr[right])) {
                set.add(arr[right]);
                result = Math.max(result, right - left + 1);
                right++;
            } else {
                set.remove(arr[left]);
                left++;
            }

        }
        return result;
    }
}
